#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // bool repeatedSubstringPattern(string s)
    // {
    //     int length = s.size();
    //     int start = 0;
    //     for (int end = 0; end < length / 2; end++)
    //     {
    //         for (int i = 0; i < length; i++)
    //         {
    //             if (s[i] == s[start])
    //             {
    //                 start++;
    //                 if (start > end)
    //                 {
    //                     start = 0;
    //                 }
    //             }
    //             else if (s[i] != s[start])
    //             {
    //                 start = 0;
    //                 break;
    //             }
    //             if (i == length - 1 && start == 0)
    //             {
    //                 return true;
    //             }
    //         }
    //     }
    //     return false;
    // }

    // bool repeatedSubstringPattern(string s)
    // {
    //     string str;
    //     str = s + s;
    //     str.erase(str.begin());
    //     str.erase(str.end() - 1);
    //     if (str.find(s) != string::npos)
    //     {
    //         return true;
    //     }
    //     else
    //     {
    //         return false;
    //     }
    // }

    void get_next(vector<int> &next, string &s)
    {
        int length = s.size();
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < length; i++)
        {
            while (j > 0 && s[i] != s[j])
            {
                j = next[j - 1];
            }
            if (s[i] == s[j])
            {
                j++;
            }
            next[i] = j;
        }
    }

    bool repeatedSubstringPattern(string s)
    {
        vector<int> next(s.size());
        get_next(next, s);
        for (auto num : next)
        {
            cout << num << " ";
        }
        cout << endl;
        int length = next.size();
        if ((next[length - 1] != 0) && (length % (length - next[length - 1]) == 0))
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

int main()
{
    string s{"abaababaab"};
    Solution sol;
    cout << sol.repeatedSubstringPattern(s) << endl;
    return 0;
}